/*
 * @lc app=leetcode.cn id=1051 lang=javascript
 *
 * [1051] 高度检查器
 */

// @lc code=start
/**
 * @param {number[]} heights
 * @return {number}
 */
var heightChecker = function (heights) {
    let heights_copy = [...heights]
    heights.sort((a, b) => a - b)
    let res = 0
    for (let i = 0; i < heights.length; i++) {
        if (heights[i] !== heights_copy[i]) res++
    }
    return res
};
// @lc code=end
var heightChecker = function (heights) {
    // 创建一个桶，index对应0-100的数值，其值代表它出现的次数
    let bucket = new Array(101).fill(0);

    // 遍历heights，对heights中所有值进行计数
    // 例如heights为[1, 1, 4, 2, 1, 3]，即可计算出其中有3个1，1个2，1个3，1个4
    for (let i = 0; i < heights.length; i++) {
        bucket[heights[i]]++;
    }

    // 统计最终未正常排序的结果
    let count = 0;

    // 按顺序遍历桶，相当于按顺序遍历了排序好的heights
    for (let i = 1, j = 0; i < bucket.length; i++) {
        // 每遍历到一个bucket[i]大于0，即为i还有数量，就将其值进行循环，
        while (bucket[i] > 0) {
            // 如果此时heights[j]的值与i的值不同，则表示该值未正确排序，即count++
            if (heights[j] !== i) {
                count++;
            }
            // 每次循环bucket[i]减1，表示i的数量减少1个
            bucket[i]--;
            // 每次i减1，都将heights数组的index加1，即j++
            j++;
        }
    }
}//桶排序
